#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
//class Solution {
//public:
//    vector<int> index;
//    vector<int> tmp;
//    vector<int> tmp1;
//
//    vector<int> countSmaller(vector<int>& nums) {
//        vector<int> counts(nums.size(), 0);
//        index.resize(nums.size());
//        tmp.resize(nums.size());
//        tmp1.resize(nums.size());
//        for (int i = 0; i < nums.size(); i++)
//        {
//            index[i] = i;
//        }
//        dfs(nums, counts, 0, nums.size() - 1);
//        return counts;
//    }
//    void dfs(vector<int>& nums, vector<int>& counts, int l, int r)
//    {
//        if (l >= r)
//            return;
//        int mid = (l + r - 1) / 2;
//        dfs(nums, counts, l, mid);
//        dfs(nums, counts, mid + 1, r);
//        int cur1 = l;
//        int cur2 = mid + 1;
//        int j = l;
//        while (cur1 <= mid && cur2 <= r)
//        {
//            if (nums[cur1] <= nums[cur2])
//            {
//                //cur2++;
//                //swap(index[l],index[cur2]);
//                tmp1[j] = index[cur2];
//                tmp[j++] = nums[cur2++];
//            }
//            else
//            {
//                if (r == 3)
//                    int i = 0;
//                counts[index[cur1]] += (r - cur2+1);
//                //swap(index[l],index[cur1]);
//                tmp1[j] = index[cur1];
//                tmp[j++] = nums[cur1++];
//                //cur1++;
//            }
//        }
//        while (cur1 <= mid)
//        {
//            tmp1[j] = index[cur1];
//            tmp[j++] = nums[cur1++];
//        }
//        while (cur2 <= r)
//        {
//            tmp1[j] = index[cur2];
//            tmp[j++] = nums[cur2++];
//        }
//        for (int i = l; i <= r; i++)
//        {
//            nums[i] = tmp[i];
//            index[i] = tmp1[i];
//        }
//    }
//};
//class Solution {
//public:
//    vector<int> tmp;
//    int reversePairs(vector<int>& nums) {
//        tmp.resize(nums.size());
//        return mergesort(nums, 0, nums.size() - 1);
//    }
//    int mergesort(vector<int>& nums, int l, int r)
//    {
//        if (l >= r)
//            return 0;
//        int mid = (l + r - 1) / 2;
//        int ret1 = mergesort(nums, l, mid);
//        int ret2 = mergesort(nums, mid + 1, r);
//        int ret = 0;
//        int cur1 = l, cur2 = mid + 1;
//        int j = l;
//        while (cur1 <= mid && cur2 <= r)
//        {
//            if (nums[cur1] > 2 * nums[cur2])
//            {
//                cur1++;
//                ret += (r - cur2 + 1);
//            }
//            else
//            {
//                cur2++;
//            }
//        }
//        cur1 = l;
//        cur2 = mid + 1;
//        while (cur1 <= mid && cur2 <= r)
//        {
//            if (nums[cur1] >= nums[cur2])
//            {
//                tmp[j++] = nums[cur1++];
//            }
//            else
//            {
//                tmp[j++] = nums[cur2++];
//            }
//        }
//        while (cur1 <= mid)
//        {
//            tmp[j++] = nums[cur1++];
//
//        }
//        while (cur2 <= r)
//        {
//            tmp[j++] = nums[cur2++];
//        }
//        for (int i = l; i < r; i++)
//        {
//            nums[i] = tmp[i];
//        }
//        return ret1 + ret2 + ret;
//    }
//};
//class Solution {
//public:
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//        if (l1 == nullptr)
//            return l2;
//        if (l2 == nullptr)
//            return l1;
//
//        ListNode* cur1 = l1;
//        ListNode* cur2 = l2;
//        ListNode* prev1 = nullptr;
//        ListNode* prev2 = nullptr;
//        ListNode* ret = nullptr;
//        ListNode* newtail = nullptr;
//        int carry = 0;
//        while (cur1 && cur2)
//        {
//            int add = cur1->val + cur2->val + carry;
//            int tmp = add % 10;
//            carry = add / 10;
//            prev1 = cur1;
//            prev2 = cur2;
//            cur1->val = tmp;
//            cur2->val = tmp;
//            cur1 = cur1->next;
//            cur2 = cur2->next;
//            ListNode* newnode = new ListNode(tmp);
//            if (ret == nullptr)
//            {
//                ret = newtail = newnode;
//            }
//            else
//            {
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//        }
//        while (cur1)
//        {
//            int add = cur1->val + carry;
//            int tmp = add % 10;
//            carry = add / 10;
//            prev1 = cur1;
//            cur1->val = tmp;
//            cur1 = cur1->next;
//            ListNode* newnode = new ListNode(tmp);
//            if (ret == nullptr)
//            {
//                ret = newtail = newnode;
//            }
//            else
//            {
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//
//        }
//        while (cur2)
//        {
//            int add = cur2->val + carry;
//            int tmp = add % 10;
//            carry = add / 10;
//            prev2 = cur2;
//            cur2->val = tmp;
//            cur2 = cur2->next;
//            ListNode* newnode = new ListNode(tmp);
//            if (ret == nullptr)
//            {
//                ret = newtail = newnode;
//            }
//            else
//            {
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//        }
//        if (carry)
//        {
//            ListNode* newnode = new ListNode(carry);
//            if (ret == nullptr)
//            {
//                ret = newtail = newnode;
//            }
//            else
//            {
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//        }
//        if (newtail)
//            newtail->next = nullptr;
//        return ret;
//
//    }
//};
struct ListNode
{
    ListNode(int val)
        :_val(val)
    {

    }

    int _val;
    ListNode* next = nullptr;
};
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        ListNode* n1 = head;
        ListNode* n2 = n1->next;
        if (n2 == nullptr)
            return head;

        ListNode* ret = n2;
        ListNode* prev = nullptr;
        while (n1 && n2)
        {
            n1->next = n2->next;
            n2->next = n1;
            if (prev == nullptr)
            {
                prev = n1;
            }
            else
            {
                prev->next = n2;
                prev = n1;
            }
            n1 = n1->next;
            if (n1 != nullptr)
                n2 = n1->next;
            else
                n2 = nullptr;
        }
        return ret;
    }
};
int main()
{
    //vector<int> nums = { 2,4,3,5,1 };
    //Solution().reversePairs(nums);
    ListNode* n1 = new ListNode(2);
    ListNode* n2 = new ListNode(5);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(6);
    ListNode* n6 = new ListNode(2);
    ListNode* n7 = new ListNode(2);

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n6;
    n6->next = n7;
    ListNode* cur = Solution().swapPairs(n1);
    while (cur)
    {
        cout << cur->_val << " ";
        cur = cur->next;
    }

    return 0;
}